package Main;

import Graph.Graph;
import Graph.GraphKind;
import Graph.MGraph;
import MiniSpanTree.MiniSpanTree_PRIM;
import SeqGraph.MatrixGraph;
import ShortestPath.ShortestPath_FLOYD;
import LList.SqList;

import java.util.Random;
import java.util.Scanner;

import static ShortestPath.ShortestPath_DIJ.dijkstra;

public class Main {
    private static final int INFINITY = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        LList.SqList L = new SqList(22);

        L.insert(0, "城市A");
        L.insert(1, "城市B");
        L.insert(2, "城市C");
        L.insert(3, "城市D");
        L.insert(4, "城市E");
        L.insert(5, "城市F");
        L.insert(6, "城市G");
        L.insert(7, "城市H");
        L.insert(8, "城市I");
        L.insert(9, "城市J");
        L.insert(10, "城市K");
        L.insert(11, "城市L");
        L.insert(12, "城市M");
        L.insert(13, "城市N");
        L.insert(14, "城市O");
        L.insert(15, "城市P");
        L.insert(16, "城市Q");
        L.insert(17, "城市R");
        L.insert(18, "城市S");
        L.insert(19, "城市T");

   
        Random rand = new Random();
        System.out.println("第1个城市" + "  " + L.get(0));
        System.out.println("");
    
        for (int j = 1; j < 20; j++) {
            System.out.println("");
            System.out.println("第" + (j + 1) + "个城市" + "  " + L.get(j));
            System.out.println(L.get(j - 1) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 2; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 2) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 3; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 3) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 4; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 4) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 5; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 5) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 6; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 6) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 7; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 7) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 8; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 8) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 9; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 9) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 10; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 10) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 11; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 11) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 12; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 12) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 13; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 13) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 14; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 14) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 15; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 15) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 16; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 16) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 17; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 17) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 18; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 18) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        for (int j = 19; j < 20; j++) {
            System.out.println("");
            System.out.println(L.get(j - 19) + "到" + L.get(j) + "这条路所需的经济代价为：" + rand.nextInt(100));
        }
        System.out.println("============================================================================");
        System.out.println("请输入要查找城市的序号(0到19的整数):");
        int i = new Scanner(System.in).nextInt();
        
        if(i<0|| i>19)
                System.out.println("该城市不存在"); 
        System.out.println("该城市是" + L.get(i));
        System.out.println("============================================================================");

        Object vexs[] = {"A", "B", "C", "D", "E", "F","G","H","I","J","K", "L", "M", "N", "O", "P","Q","R","S","T"};
        int[][] arcs = {
            {0,11,52,80,68,47, 8,34,38,40,96,73,81,47,13,55,88, 7,75,33},
            {11,0,37,13,52, 4,12,58,25,76, 9,69,21,71,12,45,84,31,90,73},
            {52,37,0,82, 5,91,59,67,40,68,51,14,76,69,14,62,66,83,77, 8},
            {80,13,82, 0,88,26,11,76,57,40,47,55,65,78,94,94,29,17,96,88},
            {68,52, 5,88, 0,52,23,55,59, 1,30,12,85,84,28,43,41,13,12,58},
            {47, 4,91,26,52, 0,90, 7,16,11,42, 9,83,31,64,20,96, 6,69,96},
            { 8,12,59,11,23,90, 0,54,24,26,96,54,52,82,80,58,45,69,98,39},
            {34,58,67,76,55, 7,54, 0,40, 7, 8,54,19,27,27,11,53,15,12,40},
            {38,25,40,57,59,16,24,40, 0,66, 3,15,61, 9,19,25,68, 6, 4,89},
            {40,76,68,40, 1,11,26, 7,66, 0,67,46,40,40,92,37,27,16, 2,84},
            {96, 9,51,45,30,42,96, 8, 3,67, 0,31,91,62,71,68,17,22,82,24},
            {73,69,14,55,12, 9,54,54,15,46,31, 0, 6,46,26,72,79,14,21,26},
            {81,21,76,65,85,83,52,19,61,40,91, 6, 0,70,95,34,65,53,30,52},
            {47,71,69,78,84,31,82,27, 9,40,62,46,70, 0,19, 2,47,74,58,85},
            {13,12,14,94,28,64,80,27,19,92,71,26,95,19, 0,27,99,21, 9,74},
            {55,45,62,94,43,20,58,11,25,37,68,72,34, 2,27,0, 1,63,13,17},
            {88,84,66,29,41,96,45,53,68,27,17,79,65,47,99, 1, 0,33,44, 8},
            { 7,31,83,17,13, 6,69,15, 6,16,72,14,53,74,21,63,33, 0,79,41},
            {75,90,77,96,12,69,98,12, 4, 2,82,21,30,58, 9,13,44,79, 0, 4},
            {33,73, 8,88,58,96,39,40,89,84,24,26,52,85,74,17, 8,41, 4, 0}};
        MGraph G = new MGraph(GraphKind.UDN, 20,20, vexs, arcs);
        ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
        floyd.FLOYD(G);
        display(floyd.getD());
        findPlace(G, floyd.getD());
        

        Object vexs1[]={"A", "B", "C", "D", "E", "F","G","H","I","J","K", "L", "M", "N", "O", "P","Q","R","S","T"};
        int [][] arcs1={
                {0,11,52,80,68,47, 8,34,38,40,96,73,81,47,13,55,88, 7,75,33},
                {11,0,37,13,52, 4,12,58,25,76, 9,69,21,71,12,45,84,31,90,73},
                {52,37,0,82, 5,91,59,67,40,68,51,14,76,69,14,62,66,83,77, 8},
                {80,13,82, 0,88,26,11,76,57,40,47,55,65,78,94,94,29,17,96,88},
                {68,52, 5,88, 0,52,23,55,59, 1,30,12,85,84,28,43,41,13,12,58},
                {47, 4,91,26,52, 0,90, 7,16,11,42, 9,83,31,64,20,96, 6,69,96},
                { 8,12,59,11,23,90, 0,54,24,26,96,54,52,82,80,58,45,69,98,39},
                {34,58,67,76,55, 7,54, 0,40, 7, 8,54,19,27,27,11,53,15,12,40},
                {38,25,40,57,59,16,24,40, 0,66, 3,15,61, 9,19,25,68, 6, 4,89},
                {40,76,68,40, 1,11,26, 7,66, 0,67,46,40,40,92,37,27,16, 2,84},
                {96, 9,51,45,30,42,96, 8, 3,67, 0,31,91,62,71,68,17,22,82,24},
                {73,69,14,55,12, 9,54,54,15,46,31, 0, 6,46,26,72,79,14,21,26},
                {81,21,76,65,85,83,52,19,61,40,91, 6, 0,70,95,34,65,53,30,52},
                {47,71,69,78,84,31,82,27, 9,40,62,46,70, 0,19, 2,47,74,58,85},
                {13,12,14,94,28,64,80,27,19,92,71,26,95,19, 0,27,99,21, 9,74},
                {55,45,62,94,43,20,58,11,25,37,68,72,34, 2,27,0, 1,63,13,17},
                {88,84,66,29,41,96,45,53,68,27,17,79,65,47,99, 1, 0,33,44, 8},
                { 7,31,83,17,13, 6,69,15, 6,16,72,14,53,74,21,63,33, 0,79,41},
                {75,90,77,96,12,69,98,12, 4, 2,82,21,30,58, 9,13,44,79, 0, 4},
                {33,73, 8,88,58,96,39,40,89,84,24,26,52,85,74,17, 8,41, 4, 0}
        };
        System.out.println("============================================================================");
        System.out.println("经济代价最小的铺设方式：  ");
        MGraph G1=new MGraph(GraphKind.UDG,20,50,vexs1,arcs1);
        Object[][]tree=new MiniSpanTree_PRIM().PRIM(G1,"A");
        for(int m=0;m<tree.length;m++)
            System.out.println(tree[m][0]+"----"+tree[m][1]);

        Graph graph;

        String[] vexs2 = {"A", "B", "C", "D", "E", "F","G","H","I","J","K", "L", "M", "N", "O", "P","Q","R","S","T"};

        int[][] arcs2 = {
            {0,11,52,80,68,47, 8,34,38,40,96,73,81,47,13,55,88, 7,75,33},
            {11,0,37,13,52, 4,12,58,25,76, 9,69,21,71,12,45,84,31,90,73},
            {52,37,0,82, 5,91,59,67,40,68,51,14,76,69,14,62,66,83,77, 8},
            {80,13,82, 0,88,26,11,76,57,40,47,55,65,78,94,94,29,17,96,88},
            {68,52, 5,88, 0,52,23,55,59, 1,30,12,85,84,28,43,41,13,12,58},
            {47, 4,91,26,52, 0,90, 7,16,11,42, 9,83,31,64,20,96, 6,69,96},
            { 8,12,59,11,23,90, 0,54,24,26,96,54,52,82,80,58,45,69,98,39},
            {34,58,67,76,55, 7,54, 0,40, 7, 8,54,19,27,27,11,53,15,12,40},
            {38,25,40,57,59,16,24,40, 0,66, 3,15,61, 9,19,25,68, 6, 4,89},
            {40,76,68,40, 1,11,26, 7,66, 0,67,46,40,40,92,37,27,16, 2,84},
            {96, 9,51,45,30,42,96, 8, 3,67, 0,31,91,62,71,68,17,22,82,24},
            {73,69,14,55,12, 9,54,54,15,46,31, 0, 6,46,26,72,79,14,21,26},
            {81,21,76,65,85,83,52,19,61,40,91, 6, 0,70,95,34,65,53,30,52},
            {47,71,69,78,84,31,82,27, 9,40,62,46,70, 0,19, 2,47,74,58,85},
            {13,12,14,94,28,64,80,27,19,92,71,26,95,19, 0,27,99,21, 9,74},
            {55,45,62,94,43,20,58,11,25,37,68,72,34, 2,27,0, 1,63,13,17},
            {88,84,66,29,41,96,45,53,68,27,17,79,65,47,99, 1, 0,33,44, 8},
            { 7,31,83,17,13, 6,69,15, 6,16,72,14,53,74,21,63,33, 0,79,41},
            {75,90,77,96,12,69,98,12, 4, 2,82,21,30,58, 9,13,44,79, 0, 4},
            {33,73, 8,88,58,96,39,40,89,84,24,26,52,85,74,17, 8,41, 4, 0}
        };
        graph = new MatrixGraph(GraphKind.UDN, 50, vexs2, arcs2);
        graph.showArcs();
        System.out.println("============================================================================");
        System.out.println("请输入城市编号(0到19的整数):");
        int q = new Scanner(System.in).nextInt();
        if(q<0|| q>19)
        System.out.println("该城市不存在");
        graph.traverseDFS(q);

        
        System.out.println("============================================================================");
        System.out.print("请输入维修队出发城市编号以及需要救援的城市编号:");//输入起点代号
        System.out.println("");
        System.out.println("(0:"+L.get(0)+")");
        System.out.println("(1:"+L.get(1)+")");
        System.out.println("(2:"+L.get(2)+")");
        System.out.println("(3:"+L.get(3)+")");
        System.out.println("(4:"+L.get(4)+")");
        System.out.println("(5:"+L.get(5)+")");
        System.out.println("(6:"+L.get(6)+")");
        System.out.println("(7:"+L.get(7)+")");
        System.out.println("(8:"+L.get(8)+")");
        System.out.println("(9:"+L.get(9)+")");
        System.out.println("(10:"+L.get(10)+")");
        System.out.println("(11:"+L.get(11)+")");
        System.out.println("(12:"+L.get(12)+")");
        System.out.println("(13:"+L.get(13)+")");
        System.out.println("(14:"+L.get(14)+")");
        System.out.println("(15:"+L.get(15)+")");
        System.out.println("(16:"+L.get(16)+")");
        System.out.println("(17:"+L.get(17)+")");
        System.out.println("(18:"+L.get(18)+")");
        System.out.println("(19:"+L.get(19)+")");


        Scanner scan = new Scanner(System.in);
        int begin = scan.nextInt();
        int end = scan.nextInt();
        if (begin>19||begin<0)
            System.out.println("这个起点城市不存在！");
        if (end>19||end<0)
            System.out.println("这个求援城市不存在！");
        int[] shortPath = dijkstra(arcs2, begin,end);
        System.out.println("从" + begin + "号城市出发到" + end + "号城市的最少经济代价为：" + shortPath[end]);
        System.out.println("============================================================================");
        
    }

  
    

    // 各城市之间的最少经济代价
        public static void display(int[][] D) {
            
            System.out.println("各城市之间的最少经济代价为：");
            for (int v = 0; v < D.length; v++) {
                for (int w = 0; w < D.length; w++)
                    System.out.print(D[v][w] + "\t");
                System.out.println();
            }
        }

    public static void findPlace(MGraph G, int[][] D) throws Exception {
        int min = INFINITY;
        int sum = 0;
        int u = -1;
        for (int v = 0; v < D.length; v++) {
            sum = 0;
            for (int w = 0; w < D.length; w++)
                sum += D[v][w];
            if (min > sum) {
                min = sum;
                u = v;
            }
        }
        System.out.println("============================================================================");
        System.out.println("通讯中心应建在" + G.getVex(u) + ",其到其他各城市铺设网络经济代价依次为：");
        for (int i = 0; i < D.length; i++)
        System.out.print(D[u][i] + "\t");       
        System.out.println("");
    }
}


